package com.example.origin.demo.suanfa.leecode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 *     1
 *    / \
 *   2   3
 *  / \   \
 * 4   5   6
 *    / \
 *   7   8
 * 中序遍历（左子树 → 根节点 → 右子树）
 * 二叉搜索树的排序：在二叉搜索树（BST）中，中序遍历可以得到一个升序排列的节点值序列。因此，中序遍历常用于将BST转换为有序数组。
 *
 * 符号表查询：对于实现符号表（键值对集合）的二叉搜索树，中序遍历可以用来按字典序输出所有的键。
 *
 * 解析树的词法分析：在编译器的词法分析阶段，中序遍历常用于从解析树中提取源代码的词法单元（如标识符、关键字、操作符等）。
 */
public class No94BinaryTreeInorderTraversal {
    public static void main(String[] args) {
        // 创建根节点
        TreeNode root = new TreeNode(1);

        // 创建根节点的左右子节点
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        // 继续创建左子树的子节点
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(8);

        // 创建右子树的子节点
        root.right.right = new TreeNode(6);

        List<Integer> integers = inorderTraversal(root);
        for (int i = 0; i < integers.size(); i++) {
            System.out.print(integers.get(i));
        }
        System.out.println();
        integers = inorderTraversal2(root);
        for (int i = 0; i < integers.size(); i++) {
            System.out.print(integers.get(i));
        }
        System.out.println();


    }

    static class TreeNode {

        Integer val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }

    }


    public static List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorderRecursive(root, result);
        return result;
    }

    private static void inorderRecursive(TreeNode node, List<Integer> list) {
        if (node == null) {
            return;
        }

        // 先遍历左子树
        inorderRecursive(node.left, list);

        // 访问当前节点
        list.add(node.val);

        // 再遍历右子树
        inorderRecursive(node.right, list);
    }

//    public static List<Integer> inorderTraversal2(TreeNode root) {
//        Stack<TreeNode> stack = new Stack<>();
//        List<Integer> result = new ArrayList<>();
//        TreeNode curr = root;
//
//        while (curr != null || !stack.isEmpty()) {
//            while (curr != null) {
//                stack.push(curr);
//                curr = curr.left;
//            }
//
//            curr = stack.pop();
//            result.add(curr.val);
//
//            curr = curr.right;
//        }
//
//        return result;
//    }

    public static List<Integer> inorderTraversal2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        TreeNode curr = root;
        while (curr!=null||!stack.isEmpty()){
            while (curr!=null){
                stack.push(curr);
                curr = curr.left;
            }
            TreeNode node = stack.pop();
            list.add(node.val);
            curr = node.right;
        }

        return list;
    }


}
